package org.example.SolutionNew001;

import java.util.Arrays;

public class Array04 {
    public static void main(String[] args) {
        Array04 a = new Array04();
        int[] nums=new int[]{1,2,3,4};
        System.out.println(Arrays.toString(a.productExceptSelf(nums)));
    }

    public int[] productExceptSelf1(int[] nums) {
        int n = nums.length;
        int[] res = new int[n];
        int[] pre = new int[n];
        int[] suff = new int[n];
        pre[0]=1;suff[n-1]=1;

        for(int i=1;i<n;i++){
            pre[i] = pre[i-1]*nums[i-1];
            suff[n-1-i]=suff[n-i]*nums[n-i];
        }

        for(int i=0;i<n;i++){
            res[i] = pre[i]*suff[i];
        }
        return res;
    }

    //原地策略
    public int[] productExceptSelf(int[] nums) {
        int n=nums.length;
        int[] res=new int[n];

        res[0]=1;
        for(int i=1;i<n;i++){
            res[i]=res[i-1]*nums[i-1];
        }

        int R=1;
        for(int i=n-1;i>=0;i--){
            res[i]=R*res[i];
            R*=nums[i];
        }
        return res;
    }
}
